/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"
using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
	treeHeight = 0;
	locateCheck = false;  // Used for the locate funtion

}


/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
	RC rc;
	if ( rc = pf.open( indexname, mode ) )
	{
		return rc;
	}
	
	//If this is a new page file, empty tree
	if ( pf.endPid() == 0 )
	{
		//Initialize first node as root.
		BTLeafNode tmpNode;
		treeHeight = 1;
		rootPid = 0;
		tmpNode.setTreeHeight(treeHeight);
		tmpNode.setNextNodePtr(0);
		tmpNode.setRoot(0);
		tmpNode.setKeyCount(0);
		tmpNode.write( 0, pf );
	}
	
	//Not new page file, tree already exists
	else
	{
		BTLeafNode tmpNode;
		tmpNode.read( 0, pf );
		rootPid = tmpNode.getRoot();
		treeHeight = tmpNode.getHeight();
	}
    return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
	//Set necessary saved variables before closing the file
	BTLeafNode tmpNode;
	tmpNode.read( 0, pf );
	tmpNode.setRoot( rootPid );
	tmpNode.setTreeHeight( treeHeight );
	tmpNode.write( 0, pf );
	return pf.close();
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
  RC open(const std::string& filename, char mode);

*/

RC BTreeIndex::insert(int key, const RecordId& rid)
{
	RC rc;
	BTLeafNode *LeafNodePtr = new BTLeafNode;
	IndexCursor insCurs;
	
	//Locate the position of insertion
	if ( rc = locate(key, insCurs) )
	{
		return rc;
	}
	
	//Populate tmp node, attempt to insert.
	LeafNodePtr->read( insCurs.pid, pf );
	rc = LeafNodePtr->insert( key, rid );
	
	//If insert failed due to full node
	if ( rc == RC_NODE_FULL )
	{
		//Allocate and populate new sibling node
		BTLeafNode *siblingPtr = new BTLeafNode;
		int sibKey;
		LeafNodePtr->insertAndSplit( key, rid, *siblingPtr, sibKey );
		
		//Clean up nextnode pointers resave nodes
		siblingPtr->setNextNodePtr( LeafNodePtr->getNextNodePtr() );
		LeafNodePtr->setNextNodePtr( pf.endPid() );
		LeafNodePtr->write( insCurs.pid, pf );
		siblingPtr->write( pf.endPid(), pf );
		
		//If new root is needed
		if ( treeHeight == 1 )
		{
			return recInsert( sibKey, 0, 1, 0 );
		}
		
		PageId parent = treeStack.top();
		treeStack.pop();
		int lastHeight = treeHeight - 1;
		return recInsert( sibKey, treeHeight - 1, parent, pf.endPid() - 1 );
		
	}
	
	//Insertion was simple, write tmp node and return
	LeafNodePtr->write( insCurs.pid, pf );
    return 0;
}

//Extends insert for recursive functionality
RC BTreeIndex::recInsert(int key, int height, const PageId pid, const PageId child)
{
	RC rc;
	BTNonLeafNode* tmpNL = new BTNonLeafNode;
	
	//base case, overflow at root, new root needed
	if ( height == 0)
	{
		//Set root and height
		rootPid = pf.endPid();
		treeHeight++;
		
		//make new nonleaf root, populate, and save it
		tmpNL->initializeRoot( child, key, pid );
		tmpNL->write( pf.endPid(), pf );
		return 0;
	}

	
	//Recursive case, overflow on nonLeaf insert
	tmpNL->read( pid, pf );
	if ( tmpNL->insert(key, child) == RC_NODE_FULL )
	{
		//Create new sibling, split child with it
		int tmpKey;
		BTNonLeafNode* tmpSibling = new BTNonLeafNode;
		tmpNL->insertAndSplit( key, child, *tmpSibling, tmpKey );
		
		//Write the new nonleaf, and the sibling
		tmpNL->write( pid, pf );
		tmpSibling->write( pf.endPid(), pf );
		
		//If the sibling node is on the last page due to new root 
		if ( height == 1 )
		{
			return recInsert( tmpKey, height - 1, pf.endPid() - 1, pid );
		}
		
		PageId tmpPid = treeStack.top();
		treeStack.pop();
		return recInsert( tmpKey, height - 1, tmpPid, pf.endPid() - 1 );
	}
	
	
	//Simple case, there was no overflow here return 0
	tmpNL->write( pid, pf );
	return 0;
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */

RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
	//Reset the stack before locating poi
	while ( !treeStack.empty() )
	{
		treeStack.pop();
	}
	
	RC rc;
	if ( rc = recLocate(searchKey, cursor, rootPid, 1) )
	{
		return rc;
	}
	return 0;
}

//Extends locate to be recursive
RC BTreeIndex::recLocate( int searchKey, IndexCursor& cursor, PageId pid, int curHeight )
{
	RC rc;
	int eid;
	
	//Simple case, we're at leaf node level
	if ( curHeight == treeHeight )
	{
		//Create temp leaf node, populate it, locate the correct eid
		BTLeafNode* tmpLeaf = new BTLeafNode;
		if ( rc = tmpLeaf->read(pid, pf) )
		{
			return rc;
		}
		if ( rc = tmpLeaf->locate(searchKey, eid) )
		{
			return rc;
		}
	}
	
	//Mid case, we're not at leaf node level
	else
	{
		//Create temp Nonleaf, populate it, add the non leaf to the stack
		BTNonLeafNode* tmpNL = new BTNonLeafNode;
		if ( rc = tmpNL->read(pid, pf) )
		{
			return rc;
		}
		this->treeStack.push(pid);
		
		//Locate the correct child pointer
		if ( rc = tmpNL->locateChildPtr( searchKey, pid ) )
		{
			return rc;
		}
		//Go recursively search children for correct key.
		return recLocate(searchKey, cursor, pid, curHeight+1);
	}
	
	//Set the cursor to the correct place
	cursor.pid = pid;
	cursor.eid = eid;
	return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
	RC rc;
	BTLeafNode *LeafNodePtr = new BTLeafNode;
	
	//Load the current position into the node
	if ( rc = LeafNodePtr->read(cursor.pid, pf) )
	{
		return rc;
	}
	
	//Check if at last node in tree.
	if ( cursor.eid >= LeafNodePtr->getKeyCount()
		 && LeafNodePtr->getNextNodePtr() == 0 )
	{
		return RC_END_OF_TREE;
	}
	
	//Load the current key and rid into output variables.
	if ( rc = LeafNodePtr->readEntry(cursor.eid, key, rid) )
	{
		return rc;
	}
	
	//Move the cursor forward.
	cursor.eid++;
	
	//Check if the cursor now points to the next node.
	if ( LeafNodePtr->getNextNodePtr() != 0
	     && cursor.eid >= LeafNodePtr->getKeyCount() )
	{
		cursor.eid = 0;
		cursor.pid = LeafNodePtr->getNextNodePtr();
	}
	
    return 0;
}

